import sun.awt.image.ImageWatched;

import java.util.LinkedList;
import java.util.List;

public class Test01 {
    List<List<Integer>> res = new LinkedList<>();
    List<List<Integer>> permute(int[] nums){
        LinkedList<Integer> track = new LinkedList<>();
        backtrack(nums,track);
        return res;
    }
    //要先弄明白：backtrack()这个方法是什么意思？——找到nums[]的所有排列顺序，并放入track中
    private void backtrack(int[] nums, LinkedList<Integer> track) {
        //触发结束条件
        if (track.size() == nums.length){
            res.add(new LinkedList<>(track));
            return;
        }
        /*如果选择路径——1，接下来选择了路径——2，，然后丢弃路径——2；
        * 然后选择路径——3，然后丢弃路径——3
        * 这个for循环的目的是分别选择每一条路径！第一次循环就是以nums[0]下标
        * 作为选择的第一条路经*/
        for (int i = 0; i < nums.length; i++) {
            //排除不合法选择
            if (track.contains(nums[i])){
                continue;
            }
            track.add(nums[i]);
            //以第一次循环为例：对nums[0]下标之后的数据进行全排列后，入链表
            backtrack(nums,track);
            //当以3（数组末尾元素）为选择路径时，触发了结束条件
            //然后在“以2为路径”的这层递归中丢弃路径3
            //然后在“以1为路径”的这层递归中丢弃路径2.回到了最上面那一层的递归中
            //此时track中只剩下了1，然后for循环开始走到？
            System.out.println("完整的一次排序为"+track);
            //然后丢弃nums[0]
            track.removeLast();
            System.out.println("丢弃最后一位时的track"+track);
        }
    }

    public static void main(String[] args) {
        Test01 test01 = new Test01();
        int[] nums = {1,2,3};
        test01.permute(nums);
//        System.out.println(test01.permute(nums));
    }
}
